/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/preimage-size-of-factorial-zeroes-function
   @Language: C++
   @Datetime: 19-05-27 15:23
   */

class Solution {
public:
	/**
	 * @param K: an integer
	 * @return: how many non-negative integers x have the property that f(x) = K
	 */
	int preimageSizeFZF(int K) {
		// Write your code here
		for(long low=0, high=K*5L+5L; low<high;){
			long mid=(high-low)/2+low, zero=0;
			for(long n=mid; n; zero+=(n/=5));
			if(zero>K) high=mid;
			else if(zero<K) low=mid+1;
			else return 5;
		}
		return 0;
	}
};
